Sudoku Solver
Understand and solve the interview question "Sudoku Solver".
We'll cover the following
Description#
Write a program to solve Sudoku by filling the empty cells. We will be given a 2D array representing a Sudoku puzzle. For a correct solution each of the digits 1-9 must only occur once in each:
- Row
- Column
- Nine 3x3 sub-boxes of the grid
Let us take a look at an example:
1 of 3
2 of 3
3 of 3
To solve the puzzle, we will only fill the empty cells. Empty cells are represented by a ‘.’. The array will be passed by reference, so we will not need to return it after solving the puzzle.
Coding exercise#
Solution#
While solving Sudoku, we will have to take care of two things. First, we place a number at an empty place. The number must not be present in that row, column, or sub-box. So, we will use constrained programming to keep track of which number we can place in a box and which not. Second, let us assume that we have filled a few empty places but, the choice of numbers was not optimal, and we will have to try some other combination. To do that, we will have to use backtracking.
Let us go over the algorithm:
- Start filling the board from
board[0][0] - If the value is not ‘.’, move on to the next position; otherwise, fill it.
- Iterate over each value from 1 to 9:
- Check if the value is not already present in that row, column, or 3x3 sub-matrix. If no, then move on to the next value; otherwise, move to the next step.
- Place the value on the board and move to the next position recursively.
- If we can not place any value from 1 to 9 on a position, then change the value filled in the previous cell and retry.
Let us take a look at an example:
1 of 8
2 of 8
3 of 8
4 of 8
5 of 8
6 of 8
7 of 8
8 of 8
Let us take a look at the solution:
Complexity measures#
| Time complexity | Space complexity |
|---|---|
Time complexity#
The time complexity is constant as the board size is fixed. Although it is fixed we must take into account the number of operations taking place. There are 9 possibilities to fill the first cell and 9x8 possibilities to fill the second one. This will make operations to fill a row and no more than operations to fill the whole board.
Space complexity#
The space complexity is constant because the board size is fixed. It stores 81 elements.
Strong Password Checker
Pacific Atlantic Water Flow